#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<vector<int>> allCellsDistOrder_0(int rows, int cols, int rCenter, int cCenter)
    {
        vector<vector<int>> ret;
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                //?
                ret.push_back({abs(rCenter-i),abs(cCenter-j)});
            }
        }
        return ret;
    }
    vector<vector<int>> allCellsDistOrder_1(int rows, int cols, int rCenter, int cCenter)
    {
        vector<vector<int>> ret;
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                ret.push_back({i, j});
            }
        }
        sort(ret.begin(), ret.end(), [=](vector<int> &a, vector<int> &b)
             { return abs(a[0] - rCenter) + abs(a[1] - cCenter) < abs(b[0] - rCenter) + abs(b[1] - cCenter); });
        return ret;
    }

    /**
     * @brief 计数排序
     *
     * @param rows
     * @param cols
     * @param rCenter
     * @param cCenter
     * @return vector<vector<int>>
     */
    vector<vector<int>> allCellsDistOrder_2(int rows, int cols, int rCenter, int cCenter)
    {

        auto dist = [](int r1, int c1, int r2, int c2) -> int
        {
            return abs(r1 - r2) + abs(c1 - c2);
        };
        int maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter);
        vector<vector<vector<int>>> bucket(maxDist + 1);

        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                int d = dist(i, j, rCenter, cCenter);
                vector<int> tmp = {i, j};
                bucket[d].push_back(move(tmp));
            }
        }
        vector<vector<int>> ret;
        for (int i = 0; i <= maxDist; i++)
        {
            for (auto &it : bucket[i])
            {
                ret.push_back(it);
            }
        }
        return ret;
    }

    vector<vector<int>> allCellsDistOrder_3(int rows, int cols, int rCenter, int cCenter)
    {

        const int dr[4] = {1, 1, -1, -1};
        const int dc[4] = {1, -1, -1, 1};

        int maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter);
        vector<vector<int>> ret;
        int row = rCenter, col = cCenter;
        ret.push_back({row, col});
        for (int dist = 1; dist <= maxDist; dist++)
        {
            row--;
            for (int i = 0; i < 4; i++)
            {
                while ((i % 2 == 0 && row != rCenter) || (i % 2 != 0 && col != cCenter))
                {
                    if (row >= 0 && row < rows && col >= 0 && col < cols)
                    {
                        ret.push_back({row, col});
                    }
                    row += dr[i];
                    col += dc[i];
                }
            }
        }
        return ret;
    }
};
int main()
{
    Solution s;
    vector<vector<int>> ans = s.allCellsDistOrder_1(2, 2, 1, 0);
    for (auto &rows : ans)
    {
        for (auto &v : rows)
        {
            cout << v << " ";
        }
        cout << endl;
    }
    return 0;
}